package com.yun.datastructure.tree.binarysearchtree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class BSTTree {

    BSTNode root;//根节点

    static class BSTNode {
        int key;
        Object value;
        BSTNode left;
        BSTNode right;

        public BSTNode(int key) {
            this.key = key;
        }

        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 查找关键字对应值
     *
     * @param key
     * @return
     */
    public Object get(int key) {
        BSTNode node = root;
        while (node != null) {
            if (key < node.key) {
                node = node.left;
            } else if (node.key < key) {
                node = node.right;
            } else {
                return node.value;
            }
        }
        return null;
    }

    private Object doGet(BSTNode node, int key) {
        if (node == null) {
            return null;
        }
        if (key < node.key) {
            return doGet(node.left, key);
        } else if (node.key < key) {
            return doGet(node.right, key);
        } else {
            return node.value;
        }
    }

    /**
     * @return
     */
    public Object min() {
        return min(root);
    }

    /**
     * @return
     */
    public Object max() {
        return max(root);
    }

    public Object min(BSTNode node) {
        if (node == null) {
            return null;
        }
        BSTNode p = node;
        while (p.left != null) {
            p = p.left;
        }
        return p.value;
    }

    private Object max(BSTNode node) {
        if (node == null) {
            return null;
        }
        BSTNode p = node;
        while (p.right != null) {
            p = p.right;
        }
        return p.value;
    }

    /**
     * 存储关键字和值
     *
     * @param key
     * @param value
     */
    public void put(int key, Object value) {
        //1.key 有 更新
        //2.key 没有 新增
        BSTNode node = root;
        BSTNode parent = null;
        while (node != null) {
            parent = node;
            if (key < node.key) {
                node = node.left;
            } else if (node.key < key) {
                node = node.right;
            } else {
                node.value = value;
                return;
            }
        }
        if (parent == null) {
            root = new BSTNode(key, value);
            return;
        }
        if (key < parent.key) {
            parent.left = new BSTNode(key, value);
        } else {
            parent.right = new BSTNode(key, value);
        }
    }

    /**
     * 查找关键字的前驱值
     *
     * @param key
     * @return 前驱值
     */
    public Object predecessor(int key) {
        BSTNode p = root;
        BSTNode ancestorFromLeft = null;
        while (p != null) {
            if (key < p.key) {
                p = p.left;
            } else if (p.key < key) {
                ancestorFromLeft = p;
                p = p.right;
            } else {
                break;
            }
        }
        //没找到节点
        if (p == null) {
            return null;
        }
        //找到节点 情况1：节点有左子树，此时前任就是左子树的最大值
        if (p.left != null) {
            return max(p.left);
        }
        //找到节点 情况2：节点没有左子树，若离它最近的，自左而来的祖先就是前任
        return ancestorFromLeft != null ?
                ancestorFromLeft.value : null;
    }

    /**
     * 查找关键字的后继值
     *
     * @param key
     * @return
     */
    public Object successor(int key) {
        BSTNode p = root;
        BSTNode ancestorFromRight = null;
        while (p != null) {
            if (key < p.key) {
                ancestorFromRight = p;
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            } else {
                break;
            }
        }
        //没找到节点
        if (p == null) {
            return null;
        }
        //找到节点 情况1：节点有右子树，此时后任就是右子树的最小值
        if (p.right != null) {
            return min(p.left);
        }
        //找到节点 情况2：节点没有左子树，若离它最近的，自左而来的祖先就是前任
        return ancestorFromRight != null ?
                ancestorFromRight.value : null;
    }

    /**
     * @param key
     * @return
     */
    public Object delete(int key) {
        BSTNode p = root;
        BSTNode parent = null;
        while (p != null) {
            if (key < p.key) {
                parent = p;
                p = p.left;
            } else if (p.key < key) {
                parent = p;
                p = p.right;
            } else {
                break;
            }
        }
        if (p == null) {
            return null;
        }
        //删除操作
        if (p.left == null) {
            //情况1
            shift(parent, p, p.right);
        } else if (p.right == null) {
            //情况2
            shift(parent, p, p.left);
        }else {
            //情况4
            //4.1被删除节点找后继
            BSTNode s=p.right;
            BSTNode sParent=p;//后继父亲
            while (s.left!=null){
                sParent=s;
                s=s.left;
            }
            //后继节点即为s
            if(sParent!=p){//不相邻
                //4.2删除和后继不相邻，处理后继的后事
                shift(sParent,s,s.right);//不可能有左孩子
                s.right=p.right;
            }
            //4.3后继取代被删除节点
            shift(parent,p,s);
            s.left=p.left;
        }
        return p.value;
    }

    /**
     * 托孤方法
     *
     * @param parent-被删除节点的父亲
     * @param deleted-被删除节点
     * @param child-被顶上去的节点
     */
    private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
        if (parent == null) {
            root = child;
        } else if (deleted == parent.left) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    }

    /**
     * 删除方法，递归实现
     * @param node
     * @param key
     * @return
     */
    private  BSTNode doDelete(BSTNode node,int key){
        if(node==null){
            return null;
        }
        if(key< node.key){
            node.left=doDelete(node.left,key);
            return node;
        }
        if(node.key<key){
            node.right=doDelete(node.right,key);
            return node;
        }
        //情况1-只有右孩子
        if(node.left==null){
            return node.right;
        }
        //情况2-只有左孩子
        if(node.right==null){
            return node.left;
        }
        //情况3-有两个孩子
        BSTNode s=node.right;
        while (s.left!=null){
            s=s.left;
        }
        s.right=doDelete(node.right,s.key);
        s.left=node.left;
        return s;
    }

    public List<Object> less(int key){
        ArrayList<Object> result=new ArrayList<>();
        BSTNode p=root;
        LinkedList<BSTNode> stack=new LinkedList<>();
        while (p!=null||!stack.isEmpty()){
            if(p!=null){
                stack.push(p);
                p=p.left;
            }else {
                BSTNode pop=stack.pop();
                //处理值
                if(pop.key<key){
                    result.add(pop.value);
                }else {
                    break;
                }
                p=pop.right;
            }
        }
        return result;
    }

    public List<Object> greater(int key){
        ArrayList<Object> result=new ArrayList<>();
        BSTNode p=root;
        LinkedList<BSTNode> stack=new LinkedList<>();
        while (p!=null||!stack.isEmpty()){
            if(p!=null){
                stack.push(p);
                p=p.right;
            }else {
                BSTNode pop=stack.pop();
                //处理值
                if(key< pop.key){
                    result.add(pop.value);
                }else {
                    break;
                }
                p=pop.left;
            }
        }
        return result;
    }

    public List<Object> between(int key1,int key2){
        ArrayList<Object> result=new ArrayList<>();
        BSTNode p=root;
        LinkedList<BSTNode> stack=new LinkedList<>();
        while (p!=null||!stack.isEmpty()){
            if(p!=null){
                stack.push(p);
                p=p.left;
            }else {
                BSTNode pop=stack.pop();
                //处理值
                if(pop.key>=key1&&pop.key<=key2){
                    result.add(pop.value);
                }else if(pop.key>key2){
                    break;
                }
                p=pop.right;
            }
        }
        return result;
    }
}
